#pragma once

#include "Graph.h"
#include <vector>
#include <queue>
#include <stack>

namespace {
	enum colors { WHITE, BLACK, GREY, WILL_GREY };

	class DefaultUserClass{
	public:
		void beforeStep(int startVertex){
		}

		void beforeWhiteVertex(int vertex, int parent){}

		void beforeGreyVertex(int toVertex, int fromVertex){}
		void beforeBlackVertex(int toVertex, int fromVertex){}

		void afterCurrentStep(int vertex, int parent){}

		void afterOverallStep(){}

		std::vector<int> afterDFS(){}
	};

	template<class T>
	void DFSStep(Graph& graph, T* userClass,
		std::stack<int>* vertexStack, std::vector<colors>* vertexColors,
		std::vector<std::vector<int> >* adjacentList,
		std::vector<std::vector<int>::iterator>* iteratorList,
		std::vector<int>* parentsList, int startVertex = -1) {
		if (startVertex == -1)
			startVertex = vertexStack->top();
		userClass->beforeWhiteVertex(startVertex, -1);
		while (!vertexStack->empty()){
			int currentVertex = vertexStack->top();

			if ((*vertexColors)[currentVertex] == WHITE){

				(*adjacentList)[currentVertex] = graph.getAdjacentList(currentVertex);
				(*iteratorList)[currentVertex] = (*adjacentList)[currentVertex].begin();
				*(vertexColors->begin() + currentVertex) = GREY;
			}

			if ((*iteratorList)[currentVertex] == (*adjacentList)[currentVertex].end()){
				vertexStack->pop();
				userClass->afterCurrentStep(currentVertex, (*parentsList)[currentVertex]);
				(*adjacentList)[currentVertex].clear();
				(*vertexColors)[currentVertex] = BLACK;
			}
			else{
				int processColor = *((*iteratorList)[currentVertex]);
				if ((*vertexColors)[processColor] == WHITE){
					userClass->beforeWhiteVertex(processColor, currentVertex);
					vertexStack->push(processColor);
					(*parentsList)[processColor] = currentVertex;
				}
				else if ((*vertexColors)[processColor] == GREY){
					userClass->beforeGreyVertex(processColor, currentVertex);
				}
				else if ((*vertexColors)[processColor] == BLACK){
					userClass->beforeBlackVertex(processColor, currentVertex);
				}
				(*iteratorList)[currentVertex] ++;
			}

		}

	}

	template<class T>
	void DFS(Graph& graph, T* userClass){
		int numberOfVertexes = graph.getVertexNum();
		std::vector<colors> vertexColors(numberOfVertexes, WHITE);
		std::stack<int> vertexStack;
		std::vector<std::vector<int> > adjacentList(numberOfVertexes);
		std::vector<std::vector<int>::iterator > iteratorList(numberOfVertexes);
		std::vector<int> parentsList(numberOfVertexes);

		for (int startVertex = 0; startVertex < numberOfVertexes; ++startVertex){
			if (vertexColors[startVertex] == WHITE){
				userClass->beforeStep(startVertex);
				vertexStack.push(startVertex);
				parentsList[startVertex] = -1; // no parent in DFS tree
				DFSStep(graph, userClass, &vertexStack, &vertexColors,
					&adjacentList, &iteratorList, &parentsList);
				userClass->afterOverallStep();
			}
		}
		userClass->afterDFS();
	}


	template<class T>
	void BFSStep(Graph& graph, T* userClass,
		std::queue<int>* vertexQueue, std::vector<colors>* vertexColors){
		while (!vertexQueue->empty()){
			int currentVertex = vertexQueue->front();
			vertexQueue->pop();
			(*vertexColors)[currentVertex] = GREY;
			std::vector<int> listAdjacents = graph.getAdjacentList(currentVertex);
			for (auto processVertex : listAdjacents){
				if ((*vertexColors)[processVertex] == WHITE){
					userClass->beforeWhiteVertex(processVertex);
					vertexQueue->push(processVertex);
					(*vertexColors)[processVertex] = WILL_GREY;
				}
				else if ((*vertexColors)[processVertex] == GREY){
					userClass->beforeGreyVertex();
				}
				else if ((*vertexColors)[processVertex] == BLACK){
					userClass->beforeBlackVertex();
				}
			}
			(*vertexColors)[currentVertex] = BLACK;
		}
	}

	template<class T>
	void BFS(Graph& graph, T* userClass){
		int numberOfVertexes = graph.getVertexNum();
		std::vector<colors> vertexColors(numberOfVertexes, WHITE);
		std::queue<int> vertexQueue;

		for (int startVertex = 0; startVertex < numberOfVertexes; ++startVertex){
			if (vertexColors[startVertex] == WHITE){
				userClass->beforeStep(startVertex);
				vertexQueue.push(startVertex);
				BFSStep(graph, userClass, &vertexQueue, &vertexColors);
				userClass->afterOverallStep();
			}
		}
		userClass->afterDFS();
	}

	class topologySortClass{
	private:
		std::vector<int> topologySortedArray_;
	public:

		//void beforeStep() {}

		void beforeStep(int vertex){}

		void beforeWhiteVertex(int vertex, int parent){}

		void beforeGreyVertex(int toVertex, int fromVertex){
			throw std::logic_error("Graph contains cycles");
		}

		void beforeBlackVertex(int toVertex, int fromVertex){}
		void afterCurrentStep(int vertex, int parent){
			topologySortedArray_.push_back(vertex);
		}

		void afterOverallStep() {}

		void afterDFS(){
			std::reverse(topologySortedArray_.begin(), topologySortedArray_.end());
			/*std::cout << "After topology sort:" << std::endl;
			for (size_t vertexNum = 0; vertexNum < topologySortedArray_.size(); ++vertexNum){
			std::cout << topologySortedArray_[vertexNum] << " ";
			}
			std::cout << std::endl;*/
		}

		std::vector<int> getTopologyOrder(){
			return topologySortedArray_;
		}
	};

	class SimpleBFSClass{
	private:
		std::vector<int> BFSOrder_;
	public:

		//void beforeStep() {}

		void beforeStep(int vertex){
			BFSOrder_.push_back(vertex);
		}

		void beforeWhiteVertex(int vertex){
			BFSOrder_.push_back(vertex);
		}


		void beforeGreyVertex(){}

		void beforeBlackVertex(){}
		void afterCurrentStep(int vertexNum = 0){}

		void afterOverallStep() {}

		void afterDFS(){}

		std::vector<int> getBFSOrder(){
			return BFSOrder_;
		}
	};

}

